package 最大二叉树;


public class Solution {
    /*
    给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
    创建一个根节点，其值为 nums 中的最大值。
    递归地在最大值 左边 的 子数组前缀上 构建左子树。
    递归地在最大值 右边 的 子数组后缀上 构建右子树。
    返回 nums 构建的 最大二叉树 。
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {

        // 递归参数：数组，数组的左右区间界限，左闭右开
        // 递归返回值：根节点
        // 递归的终止条件：left >= right （左闭右开）
        // 单层递归逻辑：寻找 left <--> right 区间中的最大值，记录索引值为index，以该值构造根节点
        // 根节点的左子树区间为：left <--> index
        // 根节点的右子树区间为：index+1 <--> right
        if(nums.length == 0){
            return null;
        }
        return build(nums, 0, nums.length);
    }
    public TreeNode build(int[] nums, int left, int right){
        if( left >= right ){
            return null;
        }
        // 找到当前区间的最大值 => 根节点
        int num = nums[left];
        int index = left;
        for (int i = left; i < right; i++) {
            if(nums[i] > num){
                index = i;
                num = nums[index];
            }
        }
        // 构建根节点
        TreeNode root = new TreeNode(num);
        // 根节点的左子树区间为：left <--> index
        root.left = build(nums, left, index);
        // 根节点的右子树区间为：index+1 <--> right
        root.right = build(nums, index+1, right);
        return root;
    }
}
